package everyday;

/**
 * @author zhangmin
 * @create 2022-04-27 15:41
 * 颜色分类
 * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * 思路：
 * 比遍历每个位置判断，用指针p0记录0的长度，用指针p1记录1的长度，当遇到1时且已经有0按照位置放好了，那p0指着的位置一定是已经换过位置的1，则需要把这个1放到何时位置
 */
public class sortColors75 {
    public void sortColors(int[] nums) {
        int n=nums.length;
        int p0=0,p1=0;
        for(int i=0;i<n;i++){
            if(nums[i]==1){
                //交换p1和i
                int temp=nums[i];
                nums[i]=nums[p1];
                nums[p1]=temp;
                p1++;
            }else if (nums[i]==0){
                //先交换p0和i
                int temp=nums[i];
                nums[i]=nums[p0];
                nums[p0]=temp;
                if (p0<p1){
                    //说明已经有了有序的1，且这个1被换到了i的位置，需要将i和p1换位置
                    int t=nums[i];
                    nums[i]=nums[p1];
                    nums[p1]=t;
                }
                p0++;p1++;
            }
        }
    }
}
